package com.atcumt.Carl.Array;

public class Array01 {

    /**
     * 二分查找
     * 条件：有序 + 无重复
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        // [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 移除元素
     * 条件：不能单独删除某个元素，只能覆盖
     */
    public int removeElement(int[] nums, int val) {
        int len = 0; // 标识有效数组长度
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }

    /**
     * 有序数组的平方
     * 方法：从后往前排, 双指针头尾比较，大值入 res
     */
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] res = new int[nums.length];
        int len = nums.length - 1;

        while (left <= right) {
            if (nums[right] + nums[left] > 0) {
                res[len--] = nums[right] * nums[right];
                right--;
            } else {
                res[len--] = nums[left] * nums[left];
                left++;
            }
        }
        return res;
    }

    /**
     * 长度最小的子数组
     * 方法：滑动窗口，不断调节子序列的起始和终止位置
     */
    public int minSubArrayLen(int target, int[] nums) {
        int start = 0;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        // window = i - start + 1
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= target) {
                res = Math.min(res, i - start + 1);
                sum -= nums[i++]; // 不断变更子序列的起始位置
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    /**
     * 水果成篮
     * map 记录窗口中两种水果的数目，count 记录窗口中水果种类数目
     */
    public int totalFruit(int[] fruits) {
        int count = 0;
        int res = 2, left = 0, right = 0;
        int len = fruits.length;

        if (len <= 2) {
            return len;
        }
        int[] map = new int[len];

        while (right < len) {
            map[fruits[right]]++;
            if (map[fruits[right]] == 1) {
                count++;
            }
            right++;
            while (count > 2) {
                map[fruits[left]]--;
                if (map[fruits[left]] == 0) {
                    count--;
                }
                left++;
            }
            res = Math.max(res, right - left);
        }
        return res;
    }

    /**
     * 最小覆盖子串
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     */
    public String minWindow(String s, String t) {
        int[] map = new int[128];

        int count = t.length();
        for (char c : t.toCharArray()) {
            map[c]++; // 记录字符串 t 中每个字符的数量
        }

        int left = 0;
        int right = 0;
        int res = Integer.MAX_VALUE;
        int start = 0; // 字符串 t 开始覆盖的位置
        while (right < s.length()) {
            if (map[s.charAt(right++)]-- > 0) {
                count--;
            }
            while (count == 0) {
                // 如果有更小的窗口就记录更小的窗口
                if (right - left < res) {
                    res = right - left;
                    start = left;
                }
                if (map[s.charAt(left++)]++ == 0) {
                    count++; // 字符串 t 的数量
                }
            }
        }

        if (res != Integer.MAX_VALUE) {
            return s.substring(start, start + res);
        }
        return "";
    }
}

